package 中等.数学;

/**
 * 给你一个整数 n ，如果你可以将 n 表示成若干个不同的三的幂之和，请你返回 true ，
 * 否则请返回 false 。
 * 对于一个整数 y ，如果存在整数 x 满足 y == 3x ，我们称这个整数 y 是三的幂。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/check-if-number-is-a-sum-of-powers-of-three
 */
public class 判断一个数字是否可以表示成三的幂的和_1780 {

    public static void main(String[] args) {

        System.out.println(checkPowersOfThree(12));

        // 7
        // 3 ...1

    }

    /**
     * 贪心+二分
     * n 的最大值为 10 的 7 次方，3 的幂次方最大为 14
     * 优先选择 3 的 a 次方 <= n 的最大次方 a，如果
     * n-=Math.pow(3,a) 使得 n == 0 ，说明符合条件
     *
     * @param n
     * @return
     */
    public static boolean checkPowersOfThree(int n) {
        int[] record = new int[15];
        for (int i = 0; i < record.length; i++) {
            record[i] = i;
        }

        int maxIdx = 14;
        while (n > 0) {
            int left = 0, right = maxIdx;
            int a = -1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                int pow = (int) Math.pow(3, record[mid]);
                if (pow == n) {
                    return true;
                } else if (pow < n) {
                    a = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            if (a == -1) {
                return false;
            }
            n -= (int) Math.pow(3, record[a]);

            for (int i = a; i < maxIdx && i != 14; i++) {
                record[i] = record[i + 1];
            }
            maxIdx--;
        }
        return false;
    }

    /**
     * 进制转换
     * 3 进制转换为 10 进件的计算过程
     * 例子： 210
     * = 0 * 3(0) + 1 * 3(1) + 2 * 3(2)
     * <p>
     * 如果 3 进制中存在 2 那么，n 不能由 3 的不同幂累加得到
     *
     * @param n
     * @return
     */
    public static boolean checkPowersOfThree2(int n) {
        while (n > 0) {
            if (n % 3 == 2) {
                return false;
            }
            n /= 3;
        }
        return true;
    }

}
